package 剑指offer;

import java.util.ArrayList;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:42:36 
* @Description：
* 
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
*/
public class A19顺时针打印矩阵 {

	
	/*
	 * 最好理解的
	 * 顺时针打印，就是不断的收缩矩阵的边界
	 * 
	 * 定义四个变量代表范围，up=0,down=列数-1，left=0,right=行数-1
	 * 
	 * 顺时针
1. 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
2. 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
3. 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
4. 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错
	 */
	
	//时间复杂度：O(n)
	//空间复杂度：O(1)
	
	 public  static ArrayList<Integer> printMatrix(int [][] matrix) {
		 ArrayList<Integer> list = new ArrayList<>();
		 
		 if(matrix==null || matrix.length==0||matrix[0].length==0) {
			 return list;
		 }
		 
		 int up=0;                //上边界
		 int down=matrix.length-1; //下边界
		 int left=0;               //左边界
		 int right=matrix[0].length-1;  //右边界
		 
		 while (true) {
			
			 //最上面的一行
			 for(int col=left;col<=right;col++) {
				 list.add(matrix[up][col]);
			 }
			 //向下逼近
			 up++;
			 //判断是否越界
			 if (up>down) {
				break;
			}
			 
			 
			 //最右一行
			 for(int row=up;row<=down;row++) {
				 list.add(matrix[row][right]);
			 }
			 //向左边逼近
			 right--;
			 //判断是否越界
			 if(left>right) {
				 break;
			 }
			 
			 //最下面一行
			 for(int col=right;col>=left;col--) {
				 list.add(matrix[down][col]);
			 }
			 //向上逼近
			 down--;
			 //判断越界
			 if (up>down) {
				break;
			}
			 
			// 最左边一行
			for (int row = down; row >= up; row--) {
				list.add(matrix[row][left]);
			}
			// 向右逼近
			left++;
			// 判断是否越界
			if (left > right) {
				break;
			}
		}
		return list;

	    }
	 public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("请输入数组行数和列数");
		int x = s.nextInt();
		int y = s.nextInt();
		int[][] awarry = new int[x][y];// 初始化数组
		for (int i = 0; i < x; i++)// 循环输入
			for (int j = 0; j < y; j++)
				awarry[i][j] = s.nextInt();
		
		ArrayList<Integer> list = printMatrix(awarry);
		System.out.println(list);
	}
}
